package com.dmall.directed.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * BellmanFord算法求解単源最短路径
 * 算法原理：
 * 1.对所有的边进行 V - 1 轮松弛操作肯定可以得到最短路径
 *    1.1 当然有的时候可能进行 小于 V - 1 轮松弛操作也可以得到最短路径，得到最短路径以后的操作都是空转
 * 2.对所有的边再进行一轮松弛操作看还能不能更新dis数组的值
 *    2.1 如果还能更新dis数组的值，就表示有负权环（对于无向有权图来说，有负权边就是有负权环），有负权环计算最短路径就没有任何意义
 *    2.2 如果不能更新dis数组的值，就表示没有负权环
 * @author: xiao1.wang
 * @date: 2022/8/30 23:29
 */
public class BellmanFord {
    /** 无向有权图 */
    private WeightedGraph G;
    /** 源点 */
    private int s;
    /** 到源点的最短距离保存到数组中 */
    private int[] dis;
    /** 路径记录 */
    private int[] pre;
    /** 是否有负权环 */
    private boolean hasNegativeCycle = false;

    public BellmanFord(WeightedGraph G, int s) {
        this.G = G;
        G.validateVertex(s);
        this.s = s;

        this.dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        this.pre = new int[G.V()];
        Arrays.fill(pre, -1);

        dis[s] = 0;
        pre[s] = s;

        for (int i = 1; i < G.V(); i++) {
            for (int v = 0; v < G.V(); v++) {
                for (int w : G.adj(v)) {
                    if (dis[v] != Integer.MAX_VALUE && dis[v] + G.getWeight(v, w) < dis[w]) {
                        dis[w] = dis[v] + G.getWeight(v, w);
                        pre[w] = v;
                    }
                }
            }
        }

        out:for (int v = 0; v < G.V(); v++) {
            for (int w : G.adj(v)) {
                if (dis[v] != Integer.MAX_VALUE && dis[v] + G.getWeight(v, w) < dis[w]) {
                    hasNegativeCycle = true;
                    break out;
                }
            }
        }
    }

    /**
     * 源点和目标点是否相连
     * @param t 目标点
     * @return 是否相连
     */
    public boolean isConnectedTo(int t) {
        G.validateVertex(t);
        return dis[t] != Integer.MAX_VALUE;
    }

    /**
     * 源点到目标点的最短距离
     * @param t 目标点
     * @return 最短距离
     */
    public int distTo(int t) {
        if (!isConnectedTo(t)) {
            throw new RuntimeException(String.format("No edge %d-%d", s, t));
        }
        if (hasNegCycle()) {
            throw new RuntimeException("exist negative cycle.");
        }
        return dis[t];
    }

    /**
     * 是否有负权环
     * @return true if exist negative cycle
     */
    public boolean hasNegCycle() {
        return hasNegativeCycle;
    }

    /**
     * 返回源点到t的路径，如果源点到t不连接，则返回空集合
     * @param t 目标点
     * @return 路径
     */
    public Iterable<Integer> path(int t) {
        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        String filename = BellmanFord.class.getClassLoader().getResource("com/dmall/directed/graph/wg2.txt").getPath();
        WeightedGraph g = new WeightedGraph(filename, true);
        BellmanFord bf = new BellmanFord(g, 0);
        if (!bf.hasNegCycle()) {
            for (int v = 0; v < g.V(); v++) {
                System.out.println(bf.s + " -> " + v + ": " + bf.distTo(v) + ", path = " + bf.path(v));
                // System.out.println(bf.s + " -> " + v + ": " + bf.distTo(v));
            }
        } else {
            System.out.println("exist negative cycle.");
        }
    }
}
